package com.ntschy.taizhou.leetcode;

import java.util.Deque;
import java.util.LinkedList;

public class _0042_Trap {
// 自己练习
//    public int trap(int[] height) {
//        int ans=0;
//        Deque<Integer> stack = new LinkedList<>();
//        int n = height.length;
//        for (int i = 0; i < n; ++i) {
//            while (!stack.isEmpty() && height[i]>height[stack.peek()]){
//                Integer top = stack.pop();
//                if(stack.isEmpty()){
//                    break;
//                }
//                Integer left = stack.peek();
//                int currWidth = i - left - 1;
//                int currHeight = Math.min(height[left], height[i]) - height[top];
//                ans+=currWidth*currHeight;
//            }
//            stack.push(i);
//        }
//        return ans;
//    }
//    作者：力扣官方题解
//    链接：https://leetcode.cn/problems/trapping-rain-water/solutions/692342/jie-yu-shui-by-leetcode-solution-tuvc/
//    来源：力扣（LeetCode）
//    著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
// 单调栈
    public int trap2(int[] height) {
        int ans = 0;
        Deque<Integer> stack = new LinkedList<Integer>();
        int n = height.length;
        for (int i = 0; i < n; ++i) {
            // 数组中第i个元素的值>  数组中索引为栈顶的对应的值
            while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
                //出栈(数组索引)
                int top = stack.pop();
                if (stack.isEmpty()) {
                    break;
                }
                int left = stack.peek();
                int currWidth = i - left - 1;
                int currHeight = Math.min(height[left], height[i]) - height[top];
                ans += currWidth * currHeight;
            }
            stack.push(i);
        }
        return ans;
    }




}
